/**
 * 快速排序（Quick Sort）
 * 快速排序是一种高效的排序算法，基于分治法（Divide and Conquer）的思想。
 * 它的核心是通过选择一个基准元素（pivot），将列表分为两部分：一部分小于基准元素，另一部分大于基准元素，然后递归地对这两部分进行排序。
 * 空间复杂度：快排利用递归，所以需要借助栈来保存每层递归调用的必要信息，平均栈的深度为log（n），最坏情况下为n。
 * 时间复杂度：由于快递排序的每层递归都将数组大致分为两个部分，而每层所需要的操作是O（n），所以快速排序的平均时间复杂度为 O(n log n)。
 * 最坏情况是数组自身有序或者逆序，这样数组的每次分区都极度不平衡，递归都必须要递归到最后一层，所以最坏情况的时间复杂度为O（n²）。
 *
 * @author Liu Yicong
 * @date 2025/9/21
 */
public class QuickSort {
	/**
	 * 对整个数组执行快速排序。
	 *
	 * @param arr 待排序的整数数组。
	 */
	public static void sort(int[] arr) {
		if (arr == null || arr.length < 2) {
			return; // 数组为空或只有一个元素时，无需排序
		}
		quickSort(arr, 0, arr.length - 1);
	}

	/**
	 * 递归执行快速排序的主要方法。
	 *
	 * @param arr  待排序的数组。
	 * @param low  子数组的起始索引。
	 * @param high 子数组的结束索引。
	 */
	private static void quickSort(int[] arr, int low, int high) {
		if (low < high) {
			// 获取主元最终位置的索引
			int pivotIndex = partition(arr, low, high);

			// 递归排序主元左边的子数组
			quickSort(arr, low, pivotIndex - 1);

			// 递归排序主元右边的子数组
			quickSort(arr, pivotIndex + 1, high);
		}
	}

	/**
	 * 分区操作（Partition）：将数组分为三部分：小于主元、主元、大于主元。
	 * 使用 Lomuto 分区方案：选择最右侧元素作为主元。
	 *
	 * @param arr  数组。
	 * @param low  分区的起始索引。
	 * @param high 分区的结束索引。
	 * @return 主元最终位置的索引。
	 */
	private static int partition(int[] arr, int low, int high) {
		// 选择主元：通常选择最右边的元素作为主元（也可以随机选择或三点取中法）
		int pivot = arr[high];

		// i 记录小于主元的元素区域的边界，初始时 i 指向 low-1
		int i = low - 1;

		// 遍历数组，将小于主元的元素移到左侧
		for (int j = low; j < high; j++) {
			// 如果当前元素小于或等于主元
			if (arr[j] <= pivot) {
				// 扩大小于主元元素的区域
				i++;
				// 交换 arr[i] 和 arr[j]，将小于主元的元素放到 i 处
				swap(arr, i, j);
			}
		}

		// 将主元（arr[high]）放置到其最终的正确位置 (i+1)
		swap(arr, i + 1, high);

		// 返回主元的新索引
		return i + 1;
	}

	/**
	 * 辅助方法：交换数组中两个索引位置的元素。
	 */
	private static void swap(int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}

	// --- 测试代码 ---
	public static void main(String[] args) {
		int[] data = {1, 8, 3, 9, 4, 5, 7, 2, 6};
		System.out.println("原始数组: " + java.util.Arrays.toString(data));

		QuickSort.sort(data);

		System.out.println("排序结果: " + java.util.Arrays.toString(data)); // 预期: [10, 30, 40, 50, 70, 80, 90]

		int[] data2 = {5, 4, 3, 2, 1};
		QuickSort.sort(data2);
		System.out.println("反序数组排序结果: " + java.util.Arrays.toString(data2)); // 预期: [1, 2, 3, 4, 5]
	}
}
